package com.ze.java.datastructure.other;

import java.util.Arrays;
import java.util.Random;

/**
 * @Author:yangzy
 * @Date:2021/4/2 11:49
 */
public class DynamicPro {

    public static int calculateMinimumHP(int[][] d) {
        int n = d.length, m = d[0].length;
        // 构造状态标识数组
        // 这里的加一是因为在计算右边界和下边界的时候就不用了特殊处理了
        int[][] f = new int[n + 1][m + 1];
        // 初始化边界中的值，设置最大就不会取到边界中的值了
        for (int i = 0; i <= n; i++) {
            Arrays.fill(f[i], Integer.MAX_VALUE);
        }
        // 初始化终点的右下端点值
        f[n][m - 1] = f[n - 1][m] = 1;

        // 状态转移
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                // 选择从右边走和从下边走，所需血量少的方向走
                int min = Math.min(f[i + 1][j], f[i][j + 1]);
                // 加上当前这格需要血量，就是最少的所需初始血量
                // 如果加上当前这格所需的血量，值小于1，说明不需要额外的初始血量，那么就将初始血量置为最小值1
                f[i][j] = Math.max(min - d[i][j], 1);
            }
        }

        return f[0][0];
    }

    public static void main(String[] args) {
        int[][] d = new int[10][10];
        Random random = new Random();
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d[0].length; j++) {
                int data = random.nextInt(10);
                if (data % 2 == 0) {
                    data *= -1;
                }
                d[i][j] = data;
                System.out.print(data + " ");
            }
            System.out.println();
        }
        System.out.println("最小初始健康值: " + calculateMinimumHP(d));
    }
}
